#include <stdio.h>
#include <stdlib.h>

// 定义节点
struct ListNode
{
    int val;
    struct ListNode *next;
};

// 创建节点
struct ListNode *createNode(int value)
{
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
    newNode->val = value;
    newNode->next = NULL;
    return newNode;
}

// 合并两个有序的链表
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2)
{
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;

    if(l1->val <= l2->val)
    {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
    else
    {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

struct ListNode *mergeLists(struct ListNode **lists, int listSize)
{
    if(listSize == 0)
    {
        return NULL;
    }

    if(listSize == 1)
    {
        return lists[0];
    }

    struct ListNode *result = lists[0];
    for(int i = 1; i < listSize; i++)
    {
        result = mergeTwoLists(result, lists[i]);
    }

    return result;
}

// 打印函数
void printList(struct ListNode *head)
{
    while(head != NULL)
    {
        printf("%d->", head->val);
        head = head->next;
    }
    printf("\n");
}

int main()
{
    // 创建链表
    struct ListNode *list1 = createNode(1);
    list1->next = createNode(3);
    list1->next->next = createNode(4);

    struct ListNode *list2 = createNode(2);
    list2->next = createNode(4);
    list2->next->next = createNode(5);

    struct ListNode *list3 = createNode(3);
    list3->next = createNode(6);
    list3->next->next = createNode(9);

    struct ListNode *lists[] = {list1, list2, list3};

    struct ListNode *result = mergeLists(lists, 3);
    printList(result);

    return 0;
}